<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
<head>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8" />

<title>Dirty Flag &middot; Optimization Patterns &middot; Game Programming Patterns</title>

<!-- Tell mobile browsers we're optimized for them and they don't need to crop
     the viewport. -->
<meta name="viewport" content="width=device-width, initial-scale=1"/>
<link rel="stylesheet" type="text/css" href="style.css" />
<link href="http://fonts.googleapis.com/css?family=Merriweather:400,400italic,700,700italic|Source+Code+Pro|Source+Sans+Pro:200,300,400,600,400italic,600italic|Rock+Salt" rel="stylesheet" type="text/css">
<script>
  (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
  (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
  m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
  })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

  ga('create', 'UA-42804721-1', 'gameprogrammingpatterns.com');
  ga('send', 'pageview');
</script>
<script src="jquery-1.10.1.min.js"></script>
<script src="script.js"></script>
</head>
<body id="top">
<div class="page sidebar">
<div class="content">
<nav class="top">
  <span class="prev">&larr; <a href="data-locality.html">Previous Chapter</a></span>
  <span class="next"><a href="object-pool.html">Next Chapter</a> &rarr;</span>
  <span class="toc">&equiv; <a href="/">The Book</a></span>
</nav>
<h1>Dirty Flag</h1>
<h1 class="book"><a href="/">Game Programming Patterns</a><span class="section"><a href="optimization-patterns.html">Optimization Patterns</a></span></h1>
<h2><a href="#intent" name="intent">Intent</a></h2>
<p><em>Avoid unnecessary work by deferring it until the result is needed.</em></p>
<h2><a href="#motivation" name="motivation">Motivation</a></h2>
<p>Many games have something called a <em>scene graph</em>. This is a big data structure
that contains all of the objects in the world. The rendering engine uses this to
determine where to draw stuff on the screen.</p>
<p>At its simplest, a scene graph is just a flat list of objects. Each object has a
model, or some other graphic primitive, and a <span
name="transform"><em>transform</em></span>. The transform describes the object&#8217;s
position, rotation, and scale in the world. To move or turn an object, we simply
change its transform.</p>
<aside name="transform">

<p>The mechanics of <em>how</em> this transform is stored and manipulated are unfortunately
out of scope here. The comically abbreviated summary is that it&#8217;s a 4x4 matrix.
You can make a single transform that combines two transforms&#8202;&mdash;&#8202;for example,
translating and then rotating an object&#8202;&mdash;&#8202;by multiplying the two matrices.</p>
<p>How and why that works is left as an exercise for the reader.</p>
</aside>

<p>When the renderer draws an object, it takes the object&#8217;s model, applies the
transform to it, and then renders it there in the world. If we had a scene
<em>bag</em> and not a scene <em>graph</em>, that would be it, and life would be simple.</p>
<p>However, most scene graphs are <span name="hierarchical"><em>hierarchical</em></span>.
An object in the graph may have a parent object that it is anchored to. In that
case, its transform is relative to the <em>parent&#8217;s</em> position and isn&#8217;t an
absolute position in the world.</p>
<p>For example, imagine our game world has a pirate ship at sea. Atop the ship&#8217;s
mast is a crow&#8217;s nest. Hunched in that crow&#8217;s nest is a pirate. Clutching the
pirate&#8217;s shoulder is a parrot. The ship&#8217;s local transform positions the ship in
the sea. The crow&#8217;s nest&#8217;s transform positions the nest on the ship, and so on.</p>
<p><span name="pirate"></span>
<img src="images/dirty-flag-pirate.png" alt="A pirate ship containing a crow's nest with a pirate in it with a parrot on his shoulder." /></p>
<aside name="pirate">

<p>Programmer art!</p>
</aside>

<p>This way, when a parent object moves, its children move with it automatically.
If we change the local transform of the ship, the crow&#8217;s nest, pirate, and
parrot go along for the ride. It would be a total <span
name="slide">headache</span> if, when the ship moved, we had to manually adjust
the transforms of all the objects on it to keep them from sliding off.</p>
<aside name="slide">

<p>To be honest, when you are at sea you <em>do</em> have to keep manually adjusting your
position to keep from sliding off. Maybe I should have chosen a drier example.</p>
</aside>

<p>But to actually draw the parrot on screen, we need to know its absolute position
in the world. I&#8217;ll call the parent-relative transform the object&#8217;s <em>local
transform</em>. To render an object, we need to know its <em>world transform</em>.</p>
<h3><a href="#local-and-world-transforms" name="local-and-world-transforms">Local and world transforms</a></h3>
<p>Calculating an object&#8217;s world transform is pretty straightforward&#8202;&mdash;&#8202;you just walk
its parent chain starting at the root all the way down to the object, combining
transforms as you go. In other words, the parrot&#8217;s world transform is:</p>
<p><span name="degenerate"></span>
<img src="images/dirty-flag-multiply.png" alt="The parrot's world position comes from multiplying the local positions for the ship, nest, pirate, and parrot." /></p>
<aside name="degenerate">

<p>In the degenerate case where the object has no parent, its local and world
transforms are equivalent.</p>
</aside>

<p>We need the world transform for every object in the world every frame, so even
though there are only a handful of matrix multiplications per model, it&#8217;s on the hot
code path where performance is critical. Keeping them up to date is tricky
because when a parent object moves, that affects the world transform of itself
and all of its children, recursively.</p>
<p>The simplest approach is to calculate transforms on the fly while
rendering. Each frame, we recursively traverse the scene graph starting at the
top of the hierarchy. For each object, we calculate its world transform right
then and draw it.</p>
<p>But this is terribly wasteful of our precious CPU juice! Many objects in the
world are <em>not</em> moving every frame. Think of all of the static geometry that
makes up the level. Recalculating their world transforms each frame even though
they haven&#8217;t changed is a waste.</p>
<h3><a href="#cached-world-transforms" name="cached-world-transforms">Cached world transforms</a></h3>
<p>The obvious answer is to <em>cache</em> it. In each object, we store its local
transform and its derived world transform. When we render, we only use the
precalculated world transform. If the object never moves, the cached transform
is always up to date and everything&#8217;s happy.</p>
<p>When an object <em>does</em> move, the simple approach is to refresh its world
transform right then. But don&#8217;t forget the hierarchy! When a parent moves, we
have to recalculate its world transform <em>and all of its children&#8217;s,
recursively</em>.</p>
<p>Imagine some busy gameplay. In a single frame, the ship gets tossed on the
ocean, the crow&#8217;s nest rocks in the wind, the pirate leans to the edge, and the
parrot hops onto his head. We changed four local transforms. If we recalculate
world transforms eagerly whenever a local transform changes, what ends up
happening?</p>
<p><span name="stars"></span>
<img src="images/dirty-flag-update-bad.png" alt="Any time an object moves, the world coordinates are recalculated eagerly and redundantly." /></p>
<aside name="stars">

<p>You can see on the lines marked &#x2605; that we&#8217;re recalculating the parrot&#8217;s
world transform <em>four</em> times when we only need the result of the final one.</p>
</aside>

<p>We only moved four objects, but we did <em>ten</em> world transform calculations.
That&#8217;s six pointless calculations that get thrown out before they are ever used
by the renderer. We calculated the parrot&#8217;s world transform <em>four</em> times, but it
is only rendered once.</p>
<p>The problem is that a world transform may depend on several local transforms.
Since we recalculate immediately each time <em>one</em> of the transforms changes, we end up
recalculating the same transform multiple times when more than one of the local
transforms it depends on changes in the same frame.</p>
<h3><a href="#deferred-recalculation" name="deferred-recalculation">Deferred recalculation</a></h3>
<p>We&#8217;ll solve this by <span name="decoupling">decoupling</span> changing local
transforms from updating the world transforms. This lets us change a bunch of
local transforms in a single batch and <em>then</em> recalculate the affected world
transform just once after all of those modifications are done, right before we
need it to render.</p>
<aside name="decoupling">

<p>It&#8217;s interesting how much of software architecture is intentionally
engineering a little slippage.</p>
</aside>

<p>To do this, we add a <em>flag</em> to each object in the graph. &#8220;Flag&#8221; and &#8220;bit&#8221; are
synonymous in programming&#8202;&mdash;&#8202;they both mean a single micron of data that can be
in one of two states. We call those &#8220;true&#8221; and &#8220;false&#8221;, or sometimes &#8220;set&#8221; and
&#8220;cleared&#8221;. I&#8217;ll use all of these interchangeably.</p>
<p>When the local transform
changes, we set it. When we need the object&#8217;s world transform, we check the
flag. If it&#8217;s set, we calculate the world transform and then clear the flag. The
flag represents, &#8220;Is the world transform out of date?&#8221; For reasons that aren&#8217;t
entirely clear, the traditional name for this &#8220;out-of-date-ness&#8221; is &#8220;dirty&#8221;.
Hence: <em>a dirty flag</em>. &#8220;Dirty bit&#8221; is an equally
<span name="specific">common</span> name for this pattern, but I figured I&#8217;d
stick with the name that didn&#8217;t seem as prurient.</p>
<aside name="specific">

<p>Wikipedia&#8217;s editors don&#8217;t have my level of self-control and went with <a href="http://en.wikipedia.org/wiki/Dirty_bit">dirty
bit</a>.</p>
</aside>

<p>If we apply this pattern and then move all of the objects in our previous
example, the game ends up doing:</p>
<p><img src="images/dirty-flag-update-good.png" alt="By deferring until all moves are done, we only recalculate once." /></p>
<p>That&#8217;s the best you could hope to do&#8202;&mdash;&#8202;the world transform for each affected
object is calculated exactly once. With only a single bit of data, this pattern
does a few things for us:</p>
<ul>
<li>
<p>It collapses modifications to multiple local transforms along an object&#8217;s
    parent chain into a single recalculation on the object.</p>
</li>
<li>
<p>It avoids recalculation on objects that didn&#8217;t move.</p>
</li>
<li>
<p>And a minor bonus: if an object gets removed before it&#8217;s rendered, it
    doesn&#8217;t calculate its world transform at all.</p>
</li>
</ul>
<h2><a href="#the-pattern" name="the-pattern">The Pattern</a></h2>
<p>A set of <strong>primary data</strong> changes over time. A set of <strong>derived data</strong> is
determined from this using some <strong>expensive process</strong>. A <strong>&#8220;dirty&#8221; flag</strong> tracks
when the derived data is out of sync with the primary data. It is <strong>set when the
primary data changes</strong>. If the flag is set when the derived data is needed, then
<strong>it is reprocessed and the flag is cleared.</strong> Otherwise, the previous <strong>cached
derived data</strong> is used.</p>
<h2><a href="#when-to-use-it" name="when-to-use-it">When to Use It</a></h2>
<p>Compared to some other patterns in this book, this one solves a pretty specific
problem. Also, like most optimizations, you should only reach for it when you
have a performance problem big enough to justify the added code complexity.</p>
<p>Dirty flags are applied to two kinds of work: <em>calculation</em> and
<em>synchronization</em>. In both cases, the process of going from the primary data to
the derived data is time-consuming or otherwise costly.</p>
<p>In our scene graph example, the process is slow because of the amount of math to
perform. When using this pattern for synchronization, on the other hand, it&#8217;s
more often that the derived data is <em>somewhere else</em>&#8202;&mdash;&#8202;either on disk or over
the network on another machine&#8202;&mdash;&#8202;and simply getting it from point A to point B
is what&#8217;s expensive.</p>
<p>There are a couple of other requirements too:</p>
<ul>
<li>
<p><strong>The primary data has to change more often than the derived data is used.</strong>
    This pattern works by avoiding processing derived data when a subsequent
    primary data change would invalidate it before it gets used. If you find
    yourself always needing that derived data after every single modification
    to the primary data, this pattern can&#8217;t help.</p>
</li>
<li>
<p><strong>It should be hard to update incrementally.</strong> Let&#8217;s say the
    pirate ship in our game can only carry so much booty. We need to
    know the total weight of everything in the hold. We
    <em>could</em> use this pattern and have a dirty flag for the total weight. Every
    time we add or remove some loot, we set the flag. When we need the
    total, we add up all of the booty and clear the flag.</p>
<p>But a simpler solution is to <em>keep a running total</em>. When we add or
remove an item, just add or remove its weight from the current total. If
we can &#8220;pay as we go&#8221; like this and keep the derived data updated, then
that&#8217;s often a better choice than using this pattern and calculating the
derived data from scratch when needed.</p>
</li>
</ul>
<p>This makes it sound like dirty flags are rarely appropriate, but you&#8217;ll
find a place here or there where they help. <span name="hacks">Searching</span>
your average game codebase for the word &#8220;dirty&#8221; will often turn up uses of this
pattern.</p>
<aside name="hacks">

<p>From my research, it also turns up a lot of comments apologizing for &#8220;dirty&#8221;
hacks.</p>
</aside>

<h2><a href="#keep-in-mind" name="keep-in-mind">Keep in Mind</a></h2>
<p>Even after you&#8217;ve convinced yourself this pattern is a good fit, there are a few
wrinkles that can cause you some discomfort.</p>
<h3><a href="#there-is-a-cost-to-deferring-for-too-long" name="there-is-a-cost-to-deferring-for-too-long">There is a cost to deferring for too long</a></h3>
<p>This pattern defers some slow work until the result is actually needed, but when
it is, it&#8217;s often needed <em>right now</em>. But the reason we&#8217;re using this pattern to
begin with is because calculating that result is slow!</p>
<p>This isn&#8217;t a problem in our example because we can still calculate world
coordinates fast enough to fit within a frame, but you can imagine other cases
where the work you&#8217;re doing is a big chunk that takes noticeable time to chew
through. If the game doesn&#8217;t <em>start</em> chewing until right when the player expects
to see the result, that can cause an unpleasant visible <span
name="gc">pause</span>.</p>
<p>Another problem with deferring is that if something goes wrong, you may fail to
do the work at all. This can be particularly problematic when you&#8217;re using this
pattern to save some state to a more persistent form.</p>
<p>For example, text editors know if your document has &#8220;unsaved changes&#8221;. That
little bullet or star in your file&#8217;s title bar is literally the dirty flag
visualized. The primary data is the open document in memory, and the derived
data is the file on disk.</p>
<p><img src="images/dirty-flag-title-bar.png" alt="A window titlebar showing the little icon representing unsaved changes." /></p>
<p>Many programs don&#8217;t save to disk until either the document is closed or the
application is exited. That&#8217;s fine most of the time, but if you accidentally
kick the power cable out, there goes your masterpiece.</p>
<p>Editors that auto-save a backup in the background are compensating specifically
for this shortcoming. The auto-save frequency is a point on the continuum
between not losing too much work when a crash occurs and not thrashing the file
system too much by saving all the time.</p>
<aside name="gc">

<p>This mirrors the different garbage collection strategies in systems that
automatically manage memory. Reference counting frees memory the second it&#8217;s no
longer needed, but it burns CPU time updating ref counts eagerly every time
references are changed.</p>
<p>Simple garbage collectors defer reclaiming memory until it&#8217;s really needed, but
the cost is the dreaded &#8220;GC pause&#8221; that can freeze your entire game until the
collector is done scouring the heap.</p>
<p>In between the two are more complex systems like deferred ref-counting and
incremental GC that reclaim memory less eagerly than pure ref-counting but more
eagerly than stop-the-world collectors.</p>
</aside>

<h3><a href="#you-have-to-make-sure-to-set-the-flag-*every*-time-the-state-changes" name="you-have-to-make-sure-to-set-the-flag-*every*-time-the-state-changes">You have to make sure to set the flag <em>every</em> time the state changes</a></h3>
<p>Since the derived data is calculated from the primary data, it&#8217;s essentially a
cache. Whenever you have cached data, the trickiest aspect of it is <span
name="cache"><em>cache invalidation</em></span>&#8202;&mdash;&#8202;correctly noting when the cache is
out of sync with its source data. In this pattern, that means setting the dirty
flag when <em>any</em> primary data changes.</p>
<aside name="cache">

<p>Phil Karlton famously said, &#8220;There are only two hard things in Computer Science:
cache invalidation and naming things.&#8221;</p>
</aside>

<p>Miss it in one place, and your program will incorrectly use stale derived data.
This leads to confused players and bugs that are very hard to track down. When you use
this pattern, you&#8217;ll have to take care that any code that modifies the primary
state also sets the dirty flag.</p>
<p>One way to mitigate this is by encapsulating modifications to the primary data
behind some interface. If anything that can change the state goes through a
single narrow API, you can set the dirty flag there and rest assured that it
won&#8217;t be missed.</p>
<h3><a href="#you-have-to-keep-the-previous-derived-data-in-memory" name="you-have-to-keep-the-previous-derived-data-in-memory">You have to keep the previous derived data in memory</a></h3>
<p><span name="sync"></span></p>
<p>When the derived data is needed and the dirty flag <em>isn&#8217;t</em> set, it uses the
previously calculated data. This is obvious, but that does imply that you have
to keep that derived data around in memory in case you end up needing it later.</p>
<aside name="sync">

<p>This isn&#8217;t much of an issue when you&#8217;re using this pattern to synchronize the
primary state to some other place. In that case, the derived data isn&#8217;t usually
in memory at all.</p>
</aside>

<p>If you weren&#8217;t using this pattern, you could calculate the derived data on the
fly whenever you needed it, then discard it when you were done. That avoids the
expense of keeping it cached in memory at the cost of having to do that
calculation every time you need the result.</p>
<p>Like many optimizations, then, this pattern <span name="trade">trades</span>
memory for speed. In return for keeping the previously calculated data in
memory, you avoid having to recalculate it when it hasn&#8217;t changed. This
trade-off makes sense when the calculation is slow and memory is cheap. When
you&#8217;ve got more time than memory on your hands, it&#8217;s better to calculate it
as needed.</p>
<aside name="trade">

<p>Conversely, compression algorithms make the opposite trade-off: they optimize
<em>space</em> at the expense of the processing time needed to decompress.</p>
</aside>

<h2><a href="#sample-code" name="sample-code">Sample Code</a></h2>
<p>Let&#8217;s assume we&#8217;ve met the surprisingly long list of requirements and see how
the pattern looks in code. As I mentioned before, the actual math behind
transform matrices is beyond the humble aims of this book, so I&#8217;ll just
encapsulate that in a class whose implementation you can presume exists
somewhere out in the &aelig;ther:</p>
<div class="codehilite"><pre><span class="k">class</span> <span class="nc">Transform</span>
<span class="p">{</span>
<span class="nl">public:</span>
  <span class="k">static</span> <span class="n">Transform</span> <span class="n">origin</span><span class="p">();</span>

  <span class="n">Transform</span> <span class="nf">combine</span><span class="p">(</span><span class="n">Transform</span><span class="o">&amp;</span> <span class="n">other</span><span class="p">);</span>
<span class="p">};</span>
</pre></div>


<p>The only operation we need here is <code>combine()</code> so that we can get an object&#8217;s
world transform by combining all of the local transforms along its parent chain.
It also has a method to get an &#8220;origin&#8221; transform&#8202;&mdash;&#8202;basically an identity
matrix that means no translation, rotation, or scaling at all.</p>
<p>Next, we&#8217;ll sketch out the class for an object in the scene graph. This is the
bare minimum we need <em>before</em> applying this pattern:</p>
<div class="codehilite"><pre><span class="k">class</span> <span class="nc">GraphNode</span>
<span class="p">{</span>
<span class="nl">public:</span>
  <span class="n">GraphNode</span><span class="p">(</span><span class="n">Mesh</span><span class="o">*</span> <span class="n">mesh</span><span class="p">)</span>
  <span class="o">:</span> <span class="n">mesh_</span><span class="p">(</span><span class="n">mesh</span><span class="p">),</span>
    <span class="n">local_</span><span class="p">(</span><span class="n">Transform</span><span class="o">::</span><span class="n">origin</span><span class="p">())</span>
  <span class="p">{}</span>

<span class="nl">private:</span>
  <span class="n">Transform</span> <span class="n">local_</span><span class="p">;</span>
  <span class="n">Mesh</span><span class="o">*</span> <span class="n">mesh_</span><span class="p">;</span>

  <span class="n">GraphNode</span><span class="o">*</span> <span class="n">children_</span><span class="p">[</span><span class="n">MAX_CHILDREN</span><span class="p">];</span>
  <span class="kt">int</span> <span class="n">numChildren_</span><span class="p">;</span>
<span class="p">};</span>
</pre></div>


<p>Each node has a local transform which describes where it is relative to its
parent. It has a mesh which is the actual graphic for the object. (We&#8217;ll allow
<code>mesh_</code> to be <code>NULL</code> too to handle non-visual nodes that are used just to group
their children.) Finally, each node has a possibly empty collection of child
nodes.</p>
<p>With this, a &#8220;scene graph&#8221; is really only a single root <code>GraphNode</code> whose
children (and grandchildren, etc.) are all of the objects in the world:</p>
<div class="codehilite"><pre><span class="n">GraphNode</span><span class="o">*</span> <span class="n">graph_</span> <span class="o">=</span> <span class="k">new</span> <span class="n">GraphNode</span><span class="p">(</span><span class="nb">NULL</span><span class="p">);</span>
<span class="c1">// Add children to root graph node...</span>
</pre></div>


<p>In order to render a scene graph, all we need to do is traverse that tree of
nodes, starting at the root, and call the following function for each node&#8217;s mesh
with the right world transform:</p>
<div class="codehilite"><pre><span class="kt">void</span> <span class="nf">renderMesh</span><span class="p">(</span><span class="n">Mesh</span><span class="o">*</span> <span class="n">mesh</span><span class="p">,</span> <span class="n">Transform</span> <span class="n">transform</span><span class="p">);</span>
</pre></div>


<p>We won&#8217;t implement this here, but if we did, it would do whatever magic the
renderer needs to draw that mesh at the given location in the world. If we can
call that correctly and efficiently on every node in the scene graph, we&#8217;re
happy.</p>
<h3><a href="#an-unoptimized-traversal" name="an-unoptimized-traversal">An unoptimized traversal</a></h3>
<p>To get our hands dirty, let&#8217;s throw together a basic traversal for rendering the
scene graph that calculates the world positions on the fly. It won&#8217;t be optimal,
but it will be simple. We&#8217;ll add a new method to <code>GraphNode</code>:</p>
<div class="codehilite"><pre><span class="kt">void</span> <span class="n">GraphNode</span><span class="o">::</span><span class="n">render</span><span class="p">(</span><span class="n">Transform</span> <span class="n">parentWorld</span><span class="p">)</span>
<span class="p">{</span>
  <span class="n">Transform</span> <span class="n">world</span> <span class="o">=</span> <span class="n">local_</span><span class="p">.</span><span class="n">combine</span><span class="p">(</span><span class="n">parentWorld</span><span class="p">);</span>

  <span class="k">if</span> <span class="p">(</span><span class="n">mesh_</span><span class="p">)</span> <span class="n">renderMesh</span><span class="p">(</span><span class="n">mesh_</span><span class="p">,</span> <span class="n">world</span><span class="p">);</span>

  <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">numChildren_</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
  <span class="p">{</span>
    <span class="n">children_</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">render</span><span class="p">(</span><span class="n">world</span><span class="p">);</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>


<p>We pass the world transform of the node&#8217;s parent into this using <code>parentWorld</code>.
With that, all that&#8217;s left to get the correct world transform of <em>this</em> node is
to combine that with its own local transform. We don&#8217;t have to walk <em>up</em> the
parent chain to calculate world transforms because we calculate as we go while
walking <em>down</em> the chain.</p>
<p>We calculate the node&#8217;s world transform and store it in <code>world</code>, then we render
the mesh, if we have one. Finally, we recurse into the child nodes, passing in
<em>this</em> node&#8217;s world transform. All in all, it&#8217;s a tight, simple recursive
method.</p>
<p>To draw an entire scene graph, we kick off the process at the root node:</p>
<div class="codehilite"><pre><span class="n">graph_</span><span class="o">-&gt;</span><span class="n">render</span><span class="p">(</span><span class="n">Transform</span><span class="o">::</span><span class="n">origin</span><span class="p">());</span>
</pre></div>


<h3><a href="#let's-get-dirty" name="let's-get-dirty">Let&#8217;s get dirty</a></h3>
<p>So this code does the right thing&#8202;&mdash;&#8202;it renders all the meshes in the right place
&#8212; but it doesn&#8217;t do it efficiently. It&#8217;s calling <code>local_.combine(parentWorld)</code>
on every node in the graph, every frame. Let&#8217;s see how this pattern fixes that.
First, we need to add two fields to <code>GraphNode</code>:</p>
<div class="codehilite"><pre><span class="k">class</span> <span class="nc">GraphNode</span>
<span class="p">{</span>
<span class="nl">public:</span>
  <span class="n">GraphNode</span><span class="p">(</span><span class="n">Mesh</span><span class="o">*</span> <span class="n">mesh</span><span class="p">)</span>
  <span class="o">:</span> <span class="n">mesh_</span><span class="p">(</span><span class="n">mesh</span><span class="p">),</span>
    <span class="n">local_</span><span class="p">(</span><span class="n">Transform</span><span class="o">::</span><span class="n">origin</span><span class="p">()),</span>
    <span class="n">dirty_</span><span class="p">(</span><span class="nb">true</span><span class="p">)</span>
  <span class="p">{}</span>

  <span class="c1">// Other methods...</span>

<span class="nl">private:</span>
  <span class="n">Transform</span> <span class="n">world_</span><span class="p">;</span>
  <span class="kt">bool</span> <span class="n">dirty_</span><span class="p">;</span>
  <span class="c1">// Other fields...</span>
<span class="p">};</span>
</pre></div>


<p>The <code>world_</code> field caches the previously calculated world transform, and
<code>dirty_</code>, of course, is the dirty flag. Note that the flag starts out <code>true</code>.
When we create a new node, we haven&#8217;t calculated its world transform yet. At
birth, it&#8217;s already out of sync with the local transform.</p>
<p>The only reason we need this pattern is because objects can <em>move</em>, so let&#8217;s add
support for that:</p>
<div class="codehilite"><pre><span class="kt">void</span> <span class="n">GraphNode</span><span class="o">::</span><span class="n">setTransform</span><span class="p">(</span><span class="n">Transform</span> <span class="n">local</span><span class="p">)</span>
<span class="p">{</span>
  <span class="n">local_</span> <span class="o">=</span> <span class="n">local</span><span class="p">;</span>
  <span class="n">dirty_</span> <span class="o">=</span> <span class="nb">true</span><span class="p">;</span>
<span class="p">}</span>
</pre></div>


<p>The important part here is that it sets the dirty flag too. Are we forgetting
anything? Right&#8202;&mdash;&#8202;the child nodes!</p>
<p>When a parent node moves, all of its children&#8217;s world coordinates are
invalidated too. But here, we aren&#8217;t setting their dirty flags. We <em>could</em> do
that, but that&#8217;s recursive and slow. Instead, we&#8217;ll do something clever when we
go to render. Let&#8217;s see:</p>
<p><span name="branch"></span></p>
<div class="codehilite"><pre><span class="kt">void</span> <span class="n">GraphNode</span><span class="o">::</span><span class="n">render</span><span class="p">(</span><span class="n">Transform</span> <span class="n">parentWorld</span><span class="p">,</span> <span class="kt">bool</span> <span class="n">dirty</span><span class="p">)</span>
<span class="p">{</span>
  <span class="n">dirty</span> <span class="o">|=</span> <span class="n">dirty_</span><span class="p">;</span>
  <span class="k">if</span> <span class="p">(</span><span class="n">dirty</span><span class="p">)</span>
  <span class="p">{</span>
    <span class="n">world_</span> <span class="o">=</span> <span class="n">local_</span><span class="p">.</span><span class="n">combine</span><span class="p">(</span><span class="n">parentWorld</span><span class="p">);</span>
    <span class="n">dirty_</span> <span class="o">=</span> <span class="nb">false</span><span class="p">;</span>
  <span class="p">}</span>

  <span class="k">if</span> <span class="p">(</span><span class="n">mesh_</span><span class="p">)</span> <span class="n">renderMesh</span><span class="p">(</span><span class="n">mesh_</span><span class="p">,</span> <span class="n">world_</span><span class="p">);</span>

  <span class="k">for</span> <span class="p">(</span><span class="kt">int</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">0</span><span class="p">;</span> <span class="n">i</span> <span class="o">&lt;</span> <span class="n">numChildren_</span><span class="p">;</span> <span class="n">i</span><span class="o">++</span><span class="p">)</span>
  <span class="p">{</span>
    <span class="n">children_</span><span class="p">[</span><span class="n">i</span><span class="p">]</span><span class="o">-&gt;</span><span class="n">render</span><span class="p">(</span><span class="n">world_</span><span class="p">,</span> <span class="n">dirty</span><span class="p">);</span>
  <span class="p">}</span>
<span class="p">}</span>
</pre></div>


<aside name="branch">

<p>There&#8217;s a subtle assumption here that the <code>if</code> check is faster than a matrix
multiply. Intuitively, you would think it is; surely testing a single bit is
faster than a bunch of floating point arithmetic.</p>
<p>However, modern CPUs are fantastically complex. They rely heavily on
<em>pipelining</em>&#8202;&mdash;&#8202;queueing up a series of sequential instructions. A branch like
our <code>if</code> here can cause a <em>branch misprediction</em> and force the CPU to lose cycles
refilling the pipeline.</p>
<p>The <a href="data-locality.html" class="pattern">Data Locality</a> chapter has
more about how modern CPUs try to go faster and how you can avoid tripping them
up like this.</p>
</aside>

<p>This is similar to the original na&iuml;ve implementation. The key changes are that
we check to see if the node is dirty before calculating the world transform and
we store the result in a field instead of a local variable. When the node is
clean, we skip <code>combine()</code> completely and use the old-but-still-correct <code>world_</code>
value.</p>
<p>The <span name="clever">clever</span> bit is that <code>dirty</code> parameter. That will
be <code>true</code> if any node above this node in the parent chain was dirty. In much the
same way that <code>parentWorld</code> updates the world transform incrementally as we
traverse down the hierarchy, <code>dirty</code> tracks the dirtiness of the parent chain.</p>
<p>This lets us avoid having to recursively mark each child&#8217;s <code>dirty_</code> flag
in <code>setTransform()</code>. Instead, we pass the parent&#8217;s dirty flag down to its
children when we render and look at that too to see if we need to recalculate
the world transform.</p>
<p>The end result here is exactly what we want: changing a node&#8217;s local transform
is just a couple of assignments, and rendering the world calculates the exact
minimum number of world transforms that have changed since the last frame.</p>
<aside name="clever">

<p>Note that this clever trick only works because <code>render()</code> is the <em>only</em> thing in
<code>GraphNode</code> that needs an up-to-date world transform. If other things accessed
it, we&#8217;d have to do something different.</p>
</aside>

<h2><a href="#design-decisions" name="design-decisions">Design Decisions</a></h2>
<p>This pattern is fairly specific, so there are only a couple of knobs to twiddle:</p>
<h3><a href="#when-is-the-dirty-flag-cleaned" name="when-is-the-dirty-flag-cleaned">When is the dirty flag cleaned?</a></h3>
<ul>
<li>
<p><strong>When the result is needed:</strong></p>
<ul>
<li>
<p><em>It avoids doing calculation entirely if the result is never used.</em> For
    primary data that changes much more frequently than the derived data is
    accessed, this can be a big win.</p>
</li>
<li>
<p><em>If the calculation is time-consuming, it can cause a noticeable pause.</em>
    Postponing the work until the player is expecting to see the result can
    affect their gameplay experience. It&#8217;s often fast enough that this
    isn&#8217;t a problem, but if it is, you&#8217;ll have to do the work earlier.</p>
</li>
</ul>
</li>
<li>
<p><strong>At well-defined checkpoints:</strong></p>
<p>Sometimes, there is a point in time or in the progression of the game where it&#8217;s
natural to do the deferred processing. For example,
we may want to save the game only when the pirate sails into port. Or the
sync point may not be part of the game mechanics. We may just want to hide the
work behind a loading screen or a cut scene.</p>
<ul>
<li>
<p><em>Doing the work doesn&#8217;t impact the user experience.</em> Unlike the previous
  option, you can often give something to
    distract the player while the game is busy processing.</p>
</li>
<li>
<p><em>You lose control over when the work happens.</em> This is sort of the
    opposite of the earlier point. You have micro-scale control over when you
    process, and can make sure the game handles it gracefully.</p>
<p>What you <em>can&#8217;t</em> do is ensure the player actually makes it to the
checkpoint or meets whatever criteria you&#8217;ve defined. If they get lost
or the game gets in a weird state, you can end up deferring
longer than you expect.</p>
</li>
</ul>
</li>
<li>
<p><strong>In the background:</strong></p>
<p>Usually, you start a fixed <span name="hysteresis">timer</span>
on the first modification and then process all of the changes that happen
between then and when the timer fires.</p>
<aside name="hysteresis">

<p>The term in human-computer interaction for an intentional delay between
when a program receives user input and when it responds is <a href="http://en.wikipedia.org/wiki/Hysteresis"><em>hysteresis</em></a>.</p>
</aside>

<ul>
<li>
<p><em>You can tune how often the work is performed.</em> By adjusting the timer
    interval, you can ensure it happens as frequently (or infrequently) as
    you want.</p>
</li>
<li>
<p><em>You can do more redundant work.</em> If the primary state only changes a
    tiny amount during the timer&#8217;s run, you can end up processing a large
    chunk of mostly unchanged data.</p>
</li>
<li>
<p><em>You need support for doing work asynchronously.</em>
    Processing the data &#8220;in the background&#8221; implies that the player can
    keep doing whatever it is that they&#8217;re doing at the same time. That
    means you&#8217;ll likely need threading or some other kind of concurrency
    support so that the game can work on the data while it&#8217;s still
    being played.</p>
<p>Since the player is likely interacting with
the same primary state that you&#8217;re processing, you&#8217;ll need to think
about making that safe for concurrent modification too.</p>
</li>
</ul>
</li>
</ul>
<h3><a href="#how-fine-grained-is-your-dirty-tracking" name="how-fine-grained-is-your-dirty-tracking">How fine-grained is your dirty tracking?</a></h3>
<p>Imagine our pirate game lets players build and customize their pirate ship.
Ships are automatically saved online so the player can resume where they left
off. We&#8217;re using dirty flags to determine which decks of the ship have been
fitted and need to be sent to the server. Each chunk of data we send to the
server contains some modified ship data and a bit of metadata describing where
on the ship this modification occurred.</p>
<ul>
<li>
<p><strong>If it&#8217;s more fine-grained:</strong></p>
<p>Say you slap a dirty flag on each tiny plank of each deck.</p>
<ul>
<li><em>You only process data that actually changed.</em> You&#8217;ll send exactly the
    facets of the ship that were modified to the server.</li>
</ul>
</li>
<li>
<p><strong>If it&#8217;s more coarse-grained:</strong></p>
<p>Alternatively, we could associate a dirty bit with each deck.
Changing anything on it marks the entire deck <span name="swab">dirty</span>.</p>
<aside name="swab">

<p>I could make some terrible joke about it needing to be swabbed here, but
I&#8217;ll refrain.</p>
</aside>

<ul>
<li>
<p><em>You end up processing unchanged data.</em> Add a single barrel to a deck
    and you&#8217;ll have to send the whole thing to the server.</p>
</li>
<li>
<p><em>Less memory is used for storing dirty flags.</em> Add ten barrels to a deck
    and you only need a single bit to track them all.</p>
</li>
<li>
<p><em>Less time is spent on fixed overhead.</em> When processing some changed data,
   there&#8217;s often a bit of fixed work you have to do on top of handling the
   data itself. In the example here, that&#8217;s the metadata required to
   identify where on the ship the changed data is. The bigger your
   processing chunks, the fewer of them there are, which means the less
   overhead you have.</p>
</li>
</ul>
</li>
</ul>
<h2><a href="#see-also" name="see-also">See Also</a></h2>
<ul>
<li>
<p>This pattern is common outside of games in browser-side web frameworks like
    <a href="http://angularjs.org/">Angular</a>. They use dirty flags to track which data
    has been changed in the browser and needs to be pushed up to the server.</p>
</li>
<li>
<p>Physics engines track which objects are in motion and which are resting.
    Since a resting body won&#8217;t move until an impulse is applied to it, they
    don&#8217;t need processing until they get touched. This &#8220;is moving&#8221; bit is a
    dirty flag to note which objects have had forces applied and need to have
    their physics resolved.</p>
</li>
</ul>
<nav>
  <span class="prev">&larr; <a href="data-locality.html">Previous Chapter</a></span>
  <span class="next"><a href="object-pool.html">Next Chapter</a> &rarr;</span>
  <span class="toc">&equiv; <a href="/">The Book</a></span>
</nav>
</div>
</div>
<footer>&copy; 2009-2014 Robert Nystrom</footer>
</body>
</html>
